package com.zyj.test.month1.day5;

/**
 * @author Yijia Zhang
 * @create 2024-04-27 01:11
 */
public class code0010 {
    public boolean isMatch(String s, String p) {
        int lenS = s.length();
        int lenP = p.length();
        int[][] dp = new int[lenS + 1][lenP + 1];
        for (int i = 0; i < lenP; i++) {
            if (i % 2 == 1) {
                if (p.charAt(i) == '*') {
                    dp[0][i + 1] = 1;
                } else {
                    break;
                }
            }
        }
        dp[0][0] = 1;
        for (int i = 1; i < lenS + 1; i++) {
            for (int j = 1; j < lenP + 1; j++) {
                char cs = s.charAt(i - 1);
                char cp = p.charAt(j - 1);
                if (cs == cp) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (cp == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (cp == '*') {
                    dp[i][j] = dp[i][j - 2] | dp[i][j - 1];
                    if (dp[i][j] == 0 && dp[i - 1][j] == 1 && (p.charAt(j - 2) == '.' || p.charAt(j - 2) == cs)) {
                        dp[i][j] = 1;
                    }
                }
            }
        }
        return dp[lenS][lenP] == 1;
    }
}
